/**
 * @program: data_structures_algorithms
 * @description: 插值查找,一般用于关键字分布比较均匀
 * @author: lld
 * @create: 2020-10-17 16:45
 **/
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9,11,12,13,45,67,89,100};
        int search = search(arr, 0, arr.length - 1, 1);
        System.out.println(search);

    }

    public static int search(int[] arr,int low,int high,int num){
        if(low>high){
            return -1;
        }
        System.out.println("执行");
//        int mid=low+(high-low)/2;//折半查找
        int mid=low+(high-low)*(num-arr[low])/(arr[high]-arr[low]);
        if(arr[mid]>num){
           return search(arr, low, mid-1, num);
        }else if(arr[mid]<num){
           return search(arr, mid+1, high, num);
        }else {
            return mid;
        }
    }
}
